Refine your search
Collections
Co-Authors
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z All
Lau, Nguyen Dinh
- On the Implementation of Goldberg's Maximum flow Algorithm in Extended Mixed Network
Abstract Views :209 |
PDF Views:106
Authors
Affiliations
1 University of Danang, Danang, VN
2 Vinaphone of Danang, VN
3 College of Transport II, Ministry of Transport, VN
1 University of Danang, Danang, VN
2 Vinaphone of Danang, VN
3 College of Transport II, Ministry of Transport, VN
Source
AIRCC's International Journal of Computer Science and Information Technology, Vol 9, No 6 (2017), Pagination: 93-102Abstract
In this paper, we solve this problem of finding maximum flow in extended mixed network by Revised preflow-push methods of Goldberg This algorithm completely different algorithm postflow-pull in [15]. However, we share some common theory with [15].Keywords
Algorithm, Maximum Flow, Extended Mixed Network, Preflow, Excess.Full Text
References
- Chien Tran Quoc. Postflow-pull methods to find maximal flow. Journal of science and technology University of DaNang, 5(40), 31-38, 2010.
- L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.
- J. Edmonds and R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM, vol. 19, no. 2, pp. 248–264, 1972.
- A. V. Goldberg and R. E. Tarjan. A new approach to the maximum flow problem. Proceedings of the eighteenth annual ACM symposium on Theory of computing. New York, NY, USA: ACM, pp. 136146, 1986.
- Robert Sedgewick. Algorithms in C Part 5: Graph Algorithms. Addison-Wesley, 2001.
- R. J. Anderson and a. C. S. Jo. On the parallel implementation of goldberg’s maximum flow algorithm. Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures. New York, NY, USA: ACM, pp. 168–177, 1992.
- D. Bader and V. Sachdeva. A cache-aware parallel implementation of the push-relabel network flow algorithm and experimental evaluation of the gap relabeling heuristic. Proceedings of the 18th ISCA International Conference on Parallel and Distributed Computing Systems, 2005.
- B. Hong. A lock-free multi-threaded algorithm for the maximum flow problem. IEEE International Parallel and Distributed Processing Symposium, 2008.
- Zhengyu He, Bo Hong. Dynamically Tuned Push-Relabel Algorithm for the Maximum Flow Problem on CPU-GPU-Hybrid Platforms. School of Electrical and Computer Engineering-Georgia Institute of Technology, 2010.
- Chien Tran Quoc, Lau Nguyen Dinh, Trinh Nguyen Thi Tu. Sequential and Parallel Algorithm by Postflow-Pull Methods to Find Maximum Flow. Proceedings 2013 13th International Conference on Computational Science and Its Applications, pp 178-181, 2013.
- Lau Nguyen Dinh, Thanh Le Manh, Chien Tran Quoc. Sequential and Parallel Algorithm by Pre-Push Methods to Find Maximum Flow. Vietnam Academy of Science and Technology AND Posts & Telecommunications Institute of Technology, special issue works Electic, Tel, IT; 51(4A) pp 109125, 2013.
- Lau Nguyen Dinh, Chien Tran Quoc and Manh Le Thanh. Parallel algorithm to divide optimal linear flow on extended traffic network. Research, Development and Application on Information & Communication Technology, Ministry of Information & Communication of Vietnam, No 3, V-1, 2014.
- Naveen Garg, Jochen Könemann. Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. SIAM J. Comput, Canada, 37(2), pp. 630-652, 2007.
- Lau Nguyen Dinh, Chien Tran Quoc, Thanh Le Manh.. Improved Computing Performance for Algorithm Finding the Shortest Path in Extended Graph. proceedings of international conference on foundations of computer science (FCS’14), pp 14-20, 2014.
- Nguyen Dinh Lau, Tran Quoc Chien, Sequential and parallel Algorithm to find maximum flow on extended mixed networks by revised postflow-pull methods, Fourth International Conference on Advanced Information Technologies and Applications (ICAITA 2015), ISSN: 2231–5403, ISBN: 978-1-921987-43-4, DOI: 10.5121/csit.2015.51501, 2015, pp. 19-28
- Improved Computing Performance for Listing Combinatorial Algorithms Using Multi-processing MPI and Thread Library
Abstract Views :248 |
PDF Views:102
Authors
Affiliations
1 University of Education and Science, University of Danang, VN
1 University of Education and Science, University of Danang, VN
Source
AIRCC's International Journal of Computer Science and Information Technology, Vol 10, No 5 (2018), Pagination: 33-48Abstract
This study builds up two parallel algorithms to improve computing performance for two listing binary and listing permutation algorithms. The problems are extremely interesting and practically applicable in many fields in our daily life. To parallel execution, we divide the data set input and allocate them to the processors. The article focuses on (i) the analysis of the research situation of the related works to compare and evaluate the existing problems of previous works, (ii) the analysis of the input data structure to divide data for the sub processors, (iii) the construction of parallel algorithms - proof of correctness and analysis of computing complexity, and (iv) experiments in multi-processing MPI and Thread library. Then the comparison of the results of the parallel algorithm with the sequential algorithm and the comparison of the execution time on different sub processors is discussed.Keywords
Parallel Algorithms, Listing Binary, Listing Permutation, Bounded Sequences, Substituend, Inversion.Full Text
References
- Nguyen Dinh Lau, Parallel algorithm list permutations,@ 2017,ISBN: 978-604-67-1009-7, 2324/11/2017, Quy Nhon, Binh Dinh, Vietnam, pp 348-353.
- Nguyen Dinh Lau, Parallel algorithm for the graph, Doctoral dissertation, University of Technology, The University of Da Nang, 2015.
- Hoang Chi Thanh, Parallel Generation of Permutations by Inversion Vectors,Proceedings of IEEERIVF International Conference on Computing and Communication Technologies, IEEE, ISBN: 9781-4673-0308-8, 2012, pp.129-132.
- Hoang Chi Thanh, Parallelizing a new algorithm for the set partition problem, Annals UMCS Information AIX, 2(2010) pp. 21-28, DOI:10.2478/v10065-010-0049-1, 2010, (http://dlibra.umcs.lublin.pl/dlibra/plain-content?id=12053)
- Hoang Chi Thanh, Nguyen Thi Thuy Loan. Nguyen Duy Ham, From Permutations to Iterative Permutations, International Journal of Computer Science Engineering and Technology, Vol 2, Issue 7, 2012, pp. 1310-1315.
- Hoang Chi Thanh, Parallel combinatorial algorithms for multi-sets and their applications, International Journal of Software Engineering and Knowledge Engineering, Vol. 23, No. 01, 2013, pp.81-99
- Hoàng Chi Thanh, Inheritance principle and some bounded sequence problems, The Journal of Computer Science and Cybernetics, T.29 S.1, 2013, pp. 79-91.
- Ivan Stojmenovic, Listing combinatorial objects in parallel, The international journal of parallel emergent and distributed systems, vol. 21, no. 2, April 2006, pp. 127–146.
- Akl, S.G., Gries, D. and Stojmenovic, I., An optimal parallel algorithm for generating combinations, Information Processing Letters, 33, 1989, pp. 135–139.
- Akl, S.G., Meijer, H. and Stojmenovi, I., An optimal systolic algorithm for generating permutations in lexicographic order, Journal of Parallel and Distributed Computing, 20(1), 1994, pp. 84–91.
- Akl, S.G. and Stojmenovic I., Parallel algorithms for generating integer partitions and compositions, The Journal of Combinatorial Mathematics and Combinatorial Computing, 13, 1983, pp. 107–120.
- Chen, G.H. and Chern, M.S., Parallel generation of permutations and combinations, BIT, 26, 1986, pp. 277–283.
- Cosnard, M. and Ferreira, A.G., Generating permutations on a VLSI suitable linear network, The Computer Journal, 32(6),1989, pp. 571–573.
- Djokic, B., Miyakawa, M., Sekiguchi, S., Semba, I. and Stojmenovic, I., Parallel algorithms for generating subsets and set partitions. In: T. Asano, T. Ibaraki, H. Imai and T. Nishizeki (Eds.) Proceedings of SIGAL International Symposium on Algorithms, Tokyo, Japan, Lecture Notes in Computer Science, Vol. 450, 1990, pp. 76–85.
- Even, S., Algorithmic Combinatorics (New York: Macmillan). Er, M.C., 1988, A parallel algorithm for cost-optimal generation of permutations of r out of n items, Journal of Information & Optimization Sciences, 9, 1973, pp. 53–56.
- Elhage, H. and Stojmenovic, I., Systolic generation of combinations from arbitrary elements, Parallel Processing Letters, 2(2/3), 1992, pp. 241–248.
- Gupta, P. and Bhattacharjee, G.P., Parallel generation of permutations, The Computer Journal, 26(2), 1983, pp. 97–105.
- Kapralski, A., New methods for the generation of permutations, combinations, and other combinatorial objects in parallel, Journal of Parallel and Distributed Computing, 17, 1993, pp. 315– 326.
- Seyed H. Roosta, Parallel Processing and Parallel Algorithms, Theory and Computation,USA,Springer 1999.
- Steve Fortune and James Wyllie, Parallelism in random access machines, STOC '78 Proceedings of the tenth annual ACM symposium on Theory ofcomputing, 1978, pp 114-118.
- Nguyen Dinh Lau, Tran Quoc Chien, Phan Phu Cuong, Le Hong Dung, On the implementation of Goldberg’s maximum Flow Algorithm in extended mixed network, International Journal of computer Science & Information Technology, Vol 9, No 6 pp. 93-102, 2017.
- Nguyen Dinh Lau, Tran Quoc Chien,Algorithm to Find Maximum Concurent Multicommodity Linear Flow with Limited Cost on Extended Traffic Network with Single Regulating Coeffitient on Two-Side Lines, The International Journal of Computer Networks & Communications, V 9 N2, pp: 57-67, 2017.
- Nguyen Dinh Lau, Tran Quoc Chien,Traveling Salesman Problem in Distributed Envirenment, Computer Sciencs & Information Technology (CSIT), Fourth International Conference on Advanced Information Technologies and Applications (ICAITA 2015), pp. 19-28, 2015.
- Peter S. Pacheco, An Introduction to Parallel Programming, Morgan Kaufmann Publishers is an imprint of Elsevier, ISBN 978-0-12-374260-5 (hardback), 2011